package com.cn.codebrush.数组;

/**
 * @Author Boolean
 * @Date 2022/5/22 15:44
 * @Version 1.0
 */
public class No4寻找两个正序数组的中位数 {
    public static void main(String[] args) {
        int[] nums1 = {1,2};
        int[] nums2 = {3,4};
        System.out.println(findMedianSortedArrays(nums1,nums2));
    }


    /**
     * 解法二
     * 3. 使用 while 从后往前比较
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int i = nums1.length-1;
        int j = nums2.length-1;
        int nums3[] = new int[nums1.length+nums2.length];
        int k = nums1.length+nums2.length-1;


        while(i>=0 && j>=0){
            if(nums1[i]<nums2[j]){
                nums3[k--] = nums2[j--];
            }else{
                nums3[k--] = nums1[i--];
            }
        }

        while(i>=0){
            nums3[k--] = nums1[i--];
        }
        while(j>=0){
            nums3[k--] = nums2[j--];
        }

        int r = nums3.length;
        if(r%2 == 0){
            int a = nums3[r/2] + nums3[r/2-1];
            double b =(double) a/2;
            return b;
        }else{
            double b =r/2;
            int c = nums3[(int)b];
            return (double)c;
        }
    }

    /**
     * 解法一  O（m+n）
     * 合并两个数组
     * 1. 使用 for 从前往后比较  2. 直接塞进新数组，然后使用排序  3. 使用 while 从后往前比较
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int p=0,q=0;
        int[] newNums = new int[m+n];
        for(int i=0;i<m+n;i++){
            if(p>=m){
                newNums[i] = nums2[q++];
            }else if(q>=n){
                newNums[i] = nums1[p++];
            }else {
                if(nums1[p] <= nums2[q]){
                    newNums[i] = nums1[p];
                    p++;
                }else {
                    newNums[i] = nums2[q];
                    q++;
                }
            }
        }

        int len = newNums.length;
        double res = newNums[0];
        if(len%2 > 0){
            res = newNums[len/2];
        }else {
            res = (newNums[len/2-1] + newNums[len/2])/2.0;
        }

        return res;
    }
}
